
public class Num10 {
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();

        // res[i][j]表示s的前i个字符与p的前j个字符是否匹配，
        // 最后结果res[sLen][pLen]表示s与p是否匹配，所以长度+1，
        // res[0][0]初始化为true
        boolean[][] res = new boolean[sLen+1][pLen+1];
        res[0][0] = true;

        for (int i = 0; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (p.charAt(j - 1) == '*'){
                    if (isCharMatch(s, p, i, j-1)){
                        res[i][j] = res[i][j-2] || res[i-1][j];
                    } else {
                        res[i][j] = res[i][j-2];
                    }
                } else {
                    if (isCharMatch(s, p, i, j)){
                        res[i][j] = res[i-1][j-1];
                    }
                }
            }
        }

        return res[sLen][pLen];
    }

    public boolean isCharMatch(String s, String p, int i, int j){
        if (i == 0 || j == 0){
            return false;
        }
        if (s.charAt(i-1) == p.charAt(j-1)){
            return true;
        } else {
            return p.charAt(j-1) == '.';
        }
    }

    public static void main(String[] args) {
        Num10 num10 = new Num10();
//        "ab"
//        ".*c"

//        "aaa"
//        "a*a"

//        "aaa"
//        "ab*a*c*a"

        System.out.println(num10.isMatch("a", ""));
    }

//    /**
//     * 半成品(改动态规划)
//     */
//    public boolean isMatch(String s, String p) {
//        return isMatch2(s, p, s.charAt(0));
//    }
//
//    private boolean isMatch2(String s, String p, char lastChar) {
//        if ("".equals(p)) {
//            return "".equals(s);
//        }
//        if ("".equals(s)) {
//            if (p.length() > 1 && p.charAt(1) == '*') {
//                return isMatch2(s, subStr(p, p.charAt(0)), lastChar);
//            }
//            if (p.length() > 0 && p.charAt(0) == lastChar) {
//                return isMatch2(s, p.substring(1), lastChar);
//            }
//            return false;
//        }
//
//        char s0 = s.charAt(0);
//        char p0 = p.charAt(0);
//        if (s0 == p0) {
//            if (p.length() < 2) {
//                return s.length() < 2;
//            }
//            if (p.charAt(1) == '*') {
//                return isMatch2(s.substring(1), p, s0);
//            }
//            return isMatch2(s.substring(1), p.substring(1), s0);
//        } else {
//            if (p0 == '.') {
//                if (p.length() > 1 && p.charAt(1) == '*') {
//                    return isMatch2("", p.substring(2), s0);
//                }
//                return isMatch2(s.substring(1), p.substring(1), s0);
//            }
//            if (p.length() < 2) {
//                return false;
//            }
//            if (p.charAt(1) == '*') {
//                return isMatch2(s, subStr(p, p.charAt(0)), lastChar);
//            }
//        }
//        return false;
//    }
//
//    private String subStr(String s, char c) {
//        if (s.length() > 0 && (s.charAt(0) == c || s.charAt(0) == '*')) {
//            return subStr(s.substring(1), c);
//        } else {
//            return s;
//        }
//    }
}
